<?php
/**
 * 插入排序 - 直接插入排序
 * O(n2)
 * @param array   $seq A list of integers
 * @return array Return sorted array
 */

function insertion_sort($seq)
{
    while (list($hole, $item) = each($seq)) {
        
        while ($hole > 0 && $seq[$hole - 1] > $item) {
            $seq[$hole] = $seq[$hole - 1];
            $hole--;
        }
        $seq[$hole] = $item;
    }

    return $seq;
}
